package com.shermanzhou.algorithm.sort;

/**
 * 插入排序：
 * 类似于抓牌的过程，左手上拿着排好序的牌，
 * 将抓到的牌与手牌从后往前比较，如果手牌笔抓到的牌大，手牌右移，
 * 直到手牌比抓到的牌小，将抓到的牌置于手牌右边.
 *
 * 适用于：基本有序的数据排序，效率高，可以达到线性排序的效率。
 * @author zhouchaoqun
 * @date 2018/10/22 下午6:11
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {10,8,4,2,7,1,5,6};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void sort(int[] arr) {
        for(int i=1; i<arr.length; i++) {
            int get = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > get) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = get;
        }
    }
}
